CODE 142. Binary Tree Postorder Traversal

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/25/2013-11-25-CODE 142 Binary Tree Postorder Traversal/

访问原文「CODE 142. Binary Tree Postorder Traversal」

Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},

1
 \
  2
 /
3

return [3,2,1].

public ArrayList<Integer> postorderTraversal(TreeNode root) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	if (null == root) {
		return new ArrayList<Integer>();
	}
	ArrayList<Integer> result = new ArrayList<Integer>();
	Stack<TreeNode> stack = new Stack<TreeNode>();
	while (!stack.isEmpty() || null != root) {
		if (null != root) {
			stack.push(root);
			root = root.left;
		} else {
			root = stack.peek();
			if (null != root.right) {
				TreeNode right = root.right;
				stack.peek().left = null;
				stack.peek().right = null;
				stack.push(right);
				root = right.left;
			} else {
				stack.pop();
				result.add(root.val);
				root = null;
			}
		}
	}
	return result;
}